package 剑指Offer._3140;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/27 22:36
 * 数组中出现次数超过一半的数字
 * 算法：摩尔投票
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 */
public class _39 {

    public int majorityElement(int[] nums) {
        int ans = -1, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {
                ans = num;
                cnt = 1;
            }
            else cnt += ans == num ? 1 : -1;
        }
        return ans;
    }

}
